public class Solution {
    public static int minCost(int[][] costs) {
        //行：第i号房子  列：颜色
        //r b g 到第i个房子染成对应颜色时的最小花费
        int m = costs.length,n = costs[0].length;
        int[] r = new int[m];
        int[] b = new int[m];
        int[] g = new int[m];
        r[0] = costs[0][0]; b[0] = costs[0][1]; g[0] = costs[0][2];
        for(int i = 1;i < m;i++) {
            r[i] = costs[i][0] + min(r[i-1],b[i-1],g[i-1]);
            b[i] = costs[i][1] + min(r[i-1],b[i-1],g[i-1]);
            g[i] = costs[i][2] + min(r[i-1],b[i-1],g[i-1]);
        }
        return min(r[m-1],b[m-1],g[m-1]);
    }

    private static int min(int x,int y,int z) {
        int tmp = Math.min(x,y);
        return Math.min(tmp,z);
    }

    public static void main(String[] args) {
        int[][] cost = {{3,5,3},{6,17,6},{7,13,18},{9,10,18}};
        System.out.println(minCost(cost));
    }

}
